home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 06 - 1990 / 06.12 Dec 90 / CleanPict Source / CleanPICT.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-09-11  |  12.1 KB  |  414 lines  |  [TEXT/KAHL]
  1. /*                                            CleanPICT.c                                            */
  2. /*
  3.  * Copyright © 1989, 1990 Martin Minow and MacTutor.
  4.  *
  5.  * You may use this software in any application and
  6.  * redistribute this source without restriction as long
  7.  * as this copyright and permission notice remains intact
  8.  * and the source is not redistributed for profit and you
  9.  * assume all responsibility for the proper operation of
  10.  * this software.
  11.  *
  12.  * Written in Think C.  Set Tabs every 2 characters.
  13.  */
  14.  
  15. /*
  16.  * Clean the picture by searching for noise blobs.  A
  17.  * noise blob is defined as an "island" of one color
  18.  * (forground or background) that is completly enclosed
  19.  * by the other color and is smaller than a threshold
  20.  * value.
  21.  *
  22.  * The algorithm uses a recursive "flooding" algorithm
  23.  * (also called a "maze walking" procedure) that uses
  24.  * several local variables.  These are defined as global
  25.  * (file local) -- a "real" implementation would define
  26.  * them in a structure that is allocated by the top-level
  27.  * function and passed as a parameter to the worker bees.
  28.  *
  29.  * At any point in the process, the do_point function
  30.  * examines the north/south/east/west neighbors of the
  31.  * current point (which is known to be in the island
  32.  * color).  If the point is not part of the island,
  33.  * or already seen, the function returns TRUE to continue
  34.  * looking.  Otherwise, this new island point is marked
  35.  * "seen" and the threshold counter incremented.  If 
  36.  * the counter exceeds threshold, the function returns
  37.  * FALSE and the cleanout fails for this point: the
  38.  * island is too big.
  39.  *
  40.  * The process concludes when any subroutine invocation
  41.  * returns FALSE (not an island), or when only background
  42.  * points remain.  A long, thin structure that extends
  43.  * beyond the edge of the seen array or outside the PICT is
  44.  * not an island.
  45.  *
  46.  * Note: this function is disgustingly unoptional and
  47.  * very slow (about 1 second per row on a Mac-SE for
  48.  * an 1800 pixel wide image).  I'm sure that a half-hour
  49.  * reading any decent graphics textbook would improve the
  50.  * code, but it only had to run once so why bother?
  51.  * Remember Gordon Bell's Law:
  52.  *    "Sometimes it's better to have 20 million instructions
  53.  *    by Friday than 20 million instructions per second."
  54.  * It's about twice as fast now, thanks to some good
  55.  * ideas from Mike Morton.
  56.  */
  57.  
  58. #include "CleanPICT.h"
  59. /*
  60.  * These two parameters were used to check performance
  61.  * improvements:
  62.  *    USE_TOOLBOX, if defined non-zero, uses the Macintosh
  63.  *        bit-manipulation functions.  If zero, CleanPict
  64.  *        uses local routines.
  65.  *    UPDATE_MAX determines how frequently changes are
  66.  *        written to the screen (1 updates each change as
  67.  *        it happens, 10 updates every tenth change, etc.).
  68.  */
  69. #define    USE_TOOLBOX    0
  70. #define UPDATE_MAX    10
  71.  
  72. /*
  73.  * Some interesting stuff in the current document -- this
  74.  * just saves lots of typing.
  75.  */
  76. #define PICT        (DOC.pictPort->portBits)
  77. #define RECT        (PICT.bounds)
  78.  
  79. #define XMID    (XMAX / 2)            /* Offset to center pixel    */
  80. #define YMID    (YMAX / 2)            /* Offset to center pixel    */
  81. /*
  82.  * The seen bit-array records the shape of the current
  83.  * island.  This keeps the recursive island search
  84.  * routine from examining the same island point twice,
  85.  * and it marks the island for later erasure.  It is
  86.  * written in this strange manner so we can use the
  87.  * compiler's structure assignment capability to clear
  88.  * it: this should be faster than a subroutine call to
  89.  * memset(),
  90.  */
  91. typedef struct {
  92.     Ulong    v[XMAX * YMAX / sizeof (Ulong) + 1];
  93. } SeenRecord;
  94. SeenRecord                seen_map;        /* This is the active map    */
  95. static SeenRecord    empty_map;    /* This clears seen_map        */
  96.  
  97. /*
  98.  * Make sure [x][y] are in range.  By adding <X,Y>MID and
  99.  * casting the value to unsigned, we can save on one
  100.  * comparison.
  101.  */
  102. #define in_seen_map(x, y) (                                                            \
  103.              (((unsigned) ((x) + XMID)) < (2 * XMID))                    \
  104.         && (((unsigned) ((y) + YMID)) < (2 * YMID))                    \
  105.     )
  106. /*
  107.  * XY() converts offsets from the current pixel into an
  108.  * index into the seen map bit-vector.  The algorithm is
  109.  *    ((y + YMID) * XMAX) + (x + XMID)
  110.  * Since XMAX is a small, constant, power of two, the
  111.  * compiler should replace it by a left-shift.  We
  112.  * do this explicitly just in case.
  113.  */
  114. #define XY(x, y) (                                                                            \
  115.         (((y) + YMID) << LOG_XMAX)                                                    \
  116.      + ((x) + XMID)                                                                                \
  117.     )
  118. /*
  119.  * These functions manipulate the seen map.  The program
  120.  * uses a single seen map for the entire process, stored
  121.  * in a global vector.  This would work even if the user
  122.  * has multiple pictures open, as the application will
  123.  * switch between pictures only after fully-processing
  124.  * a pixel.
  125.  */
  126. #if USE_TOOLBOX
  127. #define    myBitSet(i)        BitSet(seen_map.v, (i))
  128. #define myBitClr(i)        BitClr(seen_map.v, (i))
  129. #define myBitTst(i)        BitTst(seen_map.v, (i))
  130. #else
  131. static void            myBitSet(Ulong);
  132. static void            myBitClr(Ulong);
  133. static Boolean    myBitTst(Ulong);
  134. #endif
  135. #define set_seen(x, y)    myBitSet(XY(x, y))
  136. #define clr_seen(x, y)    myBitClr(XY(x, y))
  137. #define is_seen(x, y) (                                                                    \
  138.         in_seen_map(x, y) && myBitTst(XY(x, y))                            \
  139.     )
  140.  
  141. /*
  142.  * The BitOp macro is used to mung the PICT bitmap.
  143.  * Note that x and y are cast to unsigned longs.
  144.  */
  145. #define BitOp(op, x, y) (                                                                \
  146.         op(                                                                                                    \
  147.             PICT.baseAddr + ((Ulong) y) * PICT.rowBytes,            \
  148.             ((Ulong) x)                                                                                \
  149.         )                                                                                                        \
  150.     )
  151.  
  152. #define Pixel(x, y) BitOp(BitTst, x, y)
  153.  
  154. Boolean                    do_pixel(WindowPtr, int, int);
  155. void                        invert_seen_map(WindowPtr);
  156. Boolean                    ok_point(WindowPtr, Ulong, Ulong);
  157.  
  158. extern Ulong        VIA_ticks(void);
  159.  
  160. /*
  161.  * Clean out the picture.  Note: the boarder pixels
  162.  * aren't cleaned.
  163.  */
  164. void
  165. clean_picture(window, quit)
  166. WindowPtr        window;
  167. Boolean            quit;
  168. {
  169.         Boolean                this;
  170.         Ulong                    now;
  171.  
  172.         switch (DOC.state) {
  173.         case Idle:
  174.             return;
  175.         case Init:
  176.             /*
  177.              * This is a new cleanup operation.  Start from
  178.              * the top-left of the document.
  179.              */
  180.             GetDateTime(&DOC.start);
  181.             DOC.elapsed = 0;
  182.             DOC.examined = DOC.found = 0;
  183.             DOC.updateCount = 0;
  184.             DOC.updateRgn = NewRgn();
  185.             DOC.thisUpdateRgn = NewRgn();
  186.             DOC.bottom = RECT.bottom - 1;
  187.             DOC.right = RECT.right - 1;
  188.             DOC.center.v = RECT.top + 1;
  189.             DOC.center.h = RECT.left + 1;
  190.             DOC.state = Working;
  191.             DOC.dirty = TRUE;
  192.             break;
  193.         case Working:
  194.             if (quit || DOC.center.h >= DOC.right) {
  195.                 if (quit || ++DOC.center.v >= DOC.bottom) {
  196. finish:        if (DOC.updateCount > 0) {
  197.                         InvalRgn(DOC.updateRgn);
  198.                         DisposeRgn(DOC.updateRgn);
  199.                         DisposeRgn(DOC.thisUpdateRgn);
  200.                     }
  201.                     GetDateTime(&now);
  202.                     DOC.elapsed = now - DOC.start;
  203.                     SetWTitle(window, DOC.fileName);
  204.                     ARROW_CURSOR;
  205.                     SysBeep(10);
  206.                     DOC.state = Idle;
  207.                     make_about_window(window);
  208.                     quit = FALSE;
  209.                     break;
  210.                 }
  211.                 DOC.center.h = RECT.left + 1;
  212.                 DOC.island = Pixel(RECT.left, DOC.center.v);
  213.             }
  214.             /*
  215.              * Within a row, we skip over a run of the
  216.              * current pixel value, then check the pixel
  217.              * just above this one: if it's the same flavor,
  218.              * we examined this pixel when we did a previous
  219.              * row and decided it couldn't be in an island.
  220.              */
  221.             while (DOC.center.h < DOC.right) {
  222.                 this = Pixel(DOC.center.h, DOC.center.v);
  223.                 if (this != DOC.island)
  224.                     goto possible_island;
  225.                 ++DOC.center.h;
  226.             }
  227.             break;
  228. possible_island:
  229.             ++DOC.examined;                            /* Island here?        */
  230.             DOC.count = 0;                            /* No pixels yet    */
  231.             seen_map = empty_map;                /* Clear seen map    */
  232.             DOC.island = this;                    /* Island's color    */
  233.             if (do_pixel(window, 0, 0))    {    /* Here we go!    */
  234.                 invert_seen_map(window);    /* Zap the island    */
  235.                 ++DOC.found;
  236.                 /*
  237.                  * The current pixel type has changed!
  238.                  */
  239.                 DOC.island = Pixel(DOC.center.h, DOC.center.v);
  240.             }
  241.             ++DOC.center.h;
  242.             break;
  243.         }
  244. }
  245.  
  246. /*
  247.  * This is the recursive routine that does all the
  248.  * work.  It looks at the four cardinal neighbors:
  249.  *    if seen:    continue.
  250.  *    else if off the edge of the seen map: return FALSE;
  251.  *    else if marked, check whether threshold exceeded.
  252.  *        if so, return FALSE,
  253.  *        else, call do_pixel for the cardinal point:
  254.  *                if it returns false, return FALSE.
  255.  *    else (not the same color or all cardinal points
  256.  *        already seen) return TRUE.
  257.  * Thus: any invocation of do_pixel that returns FALSE
  258.  *    stops the process.
  259.  */    
  260. Boolean
  261. do_pixel(window, x, y)
  262. WindowPtr                window;
  263. register int        x;
  264. register int        y;
  265. {
  266.         Point                thePoint;
  267.  
  268.         if (in_seen_map(x, y) == FALSE)
  269.             return (FALSE);                        /* Fell off the edge        */
  270.         if (is_seen(x, y))                    /* Have we been here?        */
  271.             return (TRUE);                        /* Don't do it twice        */
  272.         /*
  273.          * This will need work if the PICT cannot be bounded
  274.          * by a normal Mac Rect.
  275.          */
  276.         thePoint.h = x + DOC.center.h;
  277.         thePoint.v = y + DOC.center.v;
  278.         if (PtInRect(thePoint, &RECT) == FALSE)
  279.             return (TRUE);                    /* Fell off the pict            */
  280.         else if (Pixel(thePoint.h, thePoint.v) != DOC.island)
  281.             return (TRUE);                    /* It's in the background    */
  282.         else {
  283.             set_seen(x, y);                    /* This is in the island    */
  284.             if (++DOC.count > DOC.threshold)
  285.                 return (FALSE);                    /* Island is too big        */
  286.             else if (do_pixel(window, x + 1, y    )
  287.                          && do_pixel(window, x,     y + 1)
  288.                          && do_pixel(window, x - 1, y    )
  289.                         && do_pixel(window, x,     y - 1))
  290.                  return (TRUE);                    /* Still in the island    */
  291.             else {
  292.                 return (FALSE);                    /* Propogate failure         */
  293.             }
  294.         }
  295. }    
  296.  
  297. /*
  298.  * The seen map describes the island: just invert it
  299.  * to clean out the island.
  300.  */
  301. void
  302. invert_seen_map(window)
  303. WindowPtr        window;
  304. {
  305.         register int            x, y;
  306.         Rect                            box;
  307.         Boolean                        seenTop = FALSE;
  308.         
  309.         for (y = -YMID; y < YMID; y++) {
  310.             for (x = -XMID; x < YMID; x++) {
  311.                 if (is_seen(x, y)) {
  312.                     if (DOC.island)
  313.                         BitOp(
  314.                             BitClr, x + DOC.center.h, y + DOC.center.v);
  315.                     else {
  316.                         BitOp(
  317.                             BitSet, x + DOC.center.h, y + DOC.center.v);
  318.                     }
  319.                     box.right = x;
  320.                     box.bottom = y;
  321.                     if (seenTop == FALSE) {
  322.                         box.left = x;
  323.                         box.top = y;
  324.                         seenTop = TRUE;
  325.                     }
  326.                 }
  327.             }
  328.         }
  329.         /*
  330.          * Track the change on the screen image.
  331.          */
  332.         OffsetRect(&box, DOC.center.h, DOC.center.v);
  333.         MapRect(                                    /* Use window environment    */
  334.             &box,                                        /* This is what changed        */
  335.             &RECT,                                    /* PICT's boundaries            */
  336.             &window->portRect                /* Map to these bounds        */
  337.         );
  338.         InsetRect(&box, -1, -1);    /* Cover the area                    */
  339.         /*
  340.          * If the update count is zero, set the update area
  341.          * to this box.  Otherwise, extend the update region
  342.          * to include this island. If the threshold has
  343.          * been reached, draw it onto the screen.  Note that
  344.          * we try to avoid the overhead of a full update
  345.          * event.  If this code changes, be sure to fix the
  346.          * algorithm in the update event handler.
  347.          */
  348.         if (DOC.updateCount++ == 0)
  349.             RectRgn(DOC.updateRgn, &box);
  350.         else {
  351.             RectRgn(DOC.thisUpdateRgn, &box);
  352.             UnionRgn(
  353.                 DOC.thisUpdateRgn, DOC.updateRgn, DOC.updateRgn);
  354.         }
  355.         if (DOC.updateCount >= UPDATE_MAX) {
  356.             CopyOSGrafPort(DOC.pictPort, window, DOC.updateRgn);
  357.             DOC.updateCount = 0;
  358.         } 
  359. }
  360.  
  361. #ifndef myBitSet
  362. /*
  363.  * These functions are adapted from a suggestion by Mike
  364.  * Morton: they implement bit set/clear/test without the
  365.  * overhead of a toolbox call.  Note that they could
  366.  * easily be written in C for portability.
  367.  */
  368.  
  369. static Boolean
  370. myBitTst(bitNum)
  371. register Ulong        bitNum;
  372. {
  373.         asm {
  374.             lea                seen_map.v,A0            ; A0 -> seen map base
  375.             move.w        bitNum,D0                    ; D0 := bit offset
  376.             lsr.w            #3,D0                            ; D0 := byte offset
  377.             add.w            D0,A0                            ; A0 -> correct byte
  378.             not.b            bitNum                        ; Flip bit numbering
  379.             moveq            #0,D0                            ; Clear result word
  380.             btst            bitNum,(A0)                ; Test the bit
  381.             sne                D0                                ; Set D0 if not equal
  382.             neg.b            D0                                ; flip result
  383.         }
  384.         /* Fall through to return result in D0                            */
  385. }
  386.  
  387. static void
  388. myBitSet(bitNum)
  389. register Ulong        bitNum;
  390. {
  391.         asm {
  392.             lea                seen_map.v,A0            ; A0 -> seen map base
  393.             move.w        bitNum,D0                    ; D0 := bit offset
  394.             lsr.w            #3,D0                            ; D0 := byte offset
  395.             add.w            D0,A0                            ; A0 -> correct byte
  396.             not.b            bitNum                        ; Flip bit numbering
  397.             bset            bitNum,(A0)                ; Set the bit
  398.         }
  399. }
  400.  
  401. static void
  402. myBitClr(bitNum)
  403. register Ulong        bitNum;
  404. {
  405.         asm {
  406.             lea                seen_map.v,A0            ; A0 -> seen map base
  407.             move.w        bitNum,D0                    ; D0 := bit offset
  408.             lsr.w            #3,D0                            ; D0 := byte offset
  409.             add.w            D0,A0                            ; A0 -> correct byte
  410.             not.b            bitNum                        ; Flip bit numbering
  411.             bclr            bitNum,(A0)                ; Set the bit
  412.         }
  413. }
  414. #endif